Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

  • The numbers can be arbitrarily large and are non-negative.
  • Converting the input string to integer is NOT allowed.
  • You should NOT use internal library such as BigInteger.

Solution:

  1. public class Solution {
  2.   public String multiply(String num1, String num2) {
  3.     if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) {
  4.       return "";
  5.     }
  7.     char[] chs1 = num1.toCharArray();
  8.     char[] chs2 = num2.toCharArray();
  10.     reverse(chs1, 0, chs1.length - 1);
  11.     reverse(chs2, 0, chs2.length - 1);
  13.     int n = chs1.length;
  14.     int m = chs2.length;
  16.     // total length won't be longer than m + n
  17.     int[] res = new int[m + n];
  19.     for (int i = 0; i < n; i++) {
  20.       int val = 0;
  21.       int d1 = (int)(chs1[i] - '0');
  23.       for (int j = 0; j < m; j++) {
  24.         int d2 = (int)(chs2[j] - '0');
  26.         val = d1 * d2 + res[i + j] + val;
  27.         res[i + j] = val % 10;
  28.         val /= 10;
  29.       }
  31.       if (val > 0) {
  32.         res[i + m] = val;
  33.       }
  34.     }
  36.     StringBuilder sb = new StringBuilder();
  37.     boolean valid = false;
  39.     for (int i = res.length - 1; i >= 0; i--) {
  40.       // ignore leading zeros
  41.       if (!valid && res[i] == 0) {
  42.         continue;
  43.       }
  45.       valid = true;
  46.       sb.append(res[i]);
  47.     }
  49.     if (sb.length() == 0) {
  50.         return "0";
  51.     }
  53.     return sb.toString();
  54.   }
  56.   void reverse(char[] chs, int lo, int hi) {
  57.     while (lo < hi) {
  58.       swap(chs, lo++, hi--);
  59.     }
  60.   }
  62.   void swap(char[] chs, int i, int j) {
  63.     char ch = chs[i];
  64.     chs[i] = chs[j];
  65.     chs[j] = ch;
  66.   }
  67. }